1. Technical Field
This disclosure relates generally to memory management in a data processing system and more specifically to dynamic measurement and adaptation of a parallel copying garbage collector in the data processing system.
2. Description of the Related Art
Parallel copying garbage collectors are commonly used as part of the memory management component of a managed runtime such as Java® VM available from IBM®, .NET available from Microsoft®, or the Glasgow Haskell Compiler (IBM is a registered trademark of International Business Machines Corp., in the United States other countries or both, Java is a registered trademark of Oracle and/or affiliates in the United States other countries or both, Microsoft is a registered trademark of Microsoft Corporation in the United States, other countries, or both).
Copying garbage collection is well known and understood in the field. Copying type of collectors have a number of advantages over mark-sweep type of collectors. A copying type of collector inherently compacts the memory heap, reducing fragmentation, and relocates objects using a technique, which naturally improves locality, thereby increasing cache utilization.
A number of design approaches have been applied to copying type collectors to parallelize the copying type of collectors enabling the collectors to effectively exploit the increasing number of computational units available in modern computers. Marlow et al. provide an excellent summary of the current approaches (S Marlow, T Harris, R P James, S Peyton Jones, “Parallel Generational-Copying Garbage Collection with a Block-Structured Heap”, ISMM '08 Proceedings of the 7th International Symposium on Memory Management, 2008). Current designs typically establish a size for a newly allocated copy block.
Problem areas of a parallel copying collector typically include work balancing, contention and fragmentation. Work balancing is a problem associated with ensuring parallel threads have sufficient work to maximally utilize respective processing resources. For example, in a parallel system with four threads to maintain optimal performance all four threads are required to perform the same amount of work. When one thread performs most of the work and the other three threads are idle, no benefit is obtained from parallelism.
In typical parallel copying collectors, each collector thread ends up wasting a certain amount of space in each destination region causing fragmentation. The fragmentation occurs because each thread allocates a block of memory in anticipation of copying into the block of memory. On average, half of the last block allocated is wasted. Additionally, small portions of intermediate blocks may be wasted when there is insufficient remaining space to copy a single object, but this type of wastage is typically minimal.
A typical approach to reducing fragmentation due to wastage in the last block allocates smaller copy blocks. However decreasing the size of the allocated blocks has an undesirable effect of increasing contention, because threads must return to the common free pool more often to replenish copy blocks. Kolodner and Petrank (E K Kolodner and E Petrank (IBM), “Parallel Copying Garbage Collection using Delayed Allocation”, Parallel Processing Letters, 2004) present a solution to fragmentation, called delayed allocation. However the proposed solution has not been widely used or confirmed in practice, and may lead to an increase in copy conflicts and contention. As the number of generations increases the fragmentation problem also increases. A typical generational garbage collector has two, or at most three, generations.
Contention is another form of problem of ensuring that interactions between parallel threads are minimized, particularly on shared resources. Common sources of contention typically include threads competing to allocate copy blocks from a shared free memory resource, and threads competing to take scanning work from a shared resource. Well-known solutions for reducing contention during allocation of copy blocks allocate larger copy blocks or allocate multiple copy blocks at once. These solutions typically have the undesirable side effect of increasing fragmentation. Contention for scanning work can be reduced with techniques including lock splitting and work stealing. In contrast, a general approach to reducing fragmentation in the literature is to reduce copy-block sizes. The proposed solution is typically not an effective solution especially as the degree of parallelism increases, because it increases contention.
For example, using another proposed solution, objects to be copied are collected together to form a group. The copy operation then copies the group of objects. In another proposed solution, a garbage collector orders object but does not address fragmentation or contention. In yet another proposed solution heap allocation is used to prevent fragmentation and increase load distribution effectiveness during garbage collection using multiple allocation chunks in each thread and segregating objects by size. The proposed solution however may typically reduce object locality and increase fragmentation as generations increase. Therefore there is a need to provide more effective solution addressing requirements of fragmentation and contention in a copying type of garbage collector.